package com.kevin.algorithm;

import com.kevin.model.BestRoute;
import com.kevin.model.Location;
import com.kevin.model.LocationShortRoute;
import com.kevin.utils.PointsRep;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Description: 贪心算法-最近距离算法
 *
 * @author kevin
 * @version V1.0
 * @date 2019/2/11 14:24
 **/
public class ShortRoute implements AlgorithmStrategy{
    private static final Logger LOGGER = LoggerFactory.getLogger(ShortRoute.class);

    private List<List<LocationShortRoute>> globalList = Collections.synchronizedList(new ArrayList<>());

    private PointsRep pointsRep = null;

    /**
     * 执行贪心算法
     * @param pointsRep
     * @return
     */
    @Override
    public Location[][] execute(PointsRep pointsRep) {
        /**
         *  赋值全局数据仓库
         */
        this.pointsRep = pointsRep;

        List<Location> locationList = this.pointsRep.getPoints();

        /**
         *   判断是否多于一个经纬度点信息
         */
        if(!(locationList!=null && locationList.size()>1)){
            return null;
        }

        /**
         *   选取第一个点作为起始点,封装对象信息
         */
        LocationShortRoute routeHeader = new LocationShortRoute();
        //设置经纬度信息
        routeHeader.setLocation(locationList.get(0));

        List<LocationShortRoute> shortRoutes= new ArrayList<>();
        shortRoutes.add(routeHeader);

        /**
         *  生成未处理的数据list
         */
        List<Location> unhandled = new ArrayList<>();
        for(int i=1;i<locationList.size();i++){
            unhandled.add(locationList.get(i));
        }

        /**
         * 执行贪心算法，将所有点串联成一个路径
         */
        snakeHandle(unhandled,shortRoutes);

        /**
         * 获取最优路径并返回结果
         */
        return getBestRoute();
    }

    /**
     * 贪心算法，有可能返回多条路径
     * 执行起来就如贪吃蛇
     *
     * @param unhandled
     * @param shortRoutes
     * @return
     */
    private void snakeHandle(List<Location> unhandled, List<LocationShortRoute> shortRoutes){
        int routesSize = shortRoutes.size();
        //蛇头
        LocationShortRoute header = shortRoutes.get(routesSize-1);

        if(unhandled!=null && unhandled.size()>1){
            /**
             *  查找当前点到其他未遍历的最近的点
             */
            //未遍历点下标
            int index = 0;
            //最短距离
            BigDecimal dis = this.pointsRep.getDis(header.getLocation().getId(),unhandled.get(index).getId());

            for(int i=1;i<unhandled.size();i++){
                BigDecimal tempDis = this.pointsRep.getDis(header.getLocation().getId(),unhandled.get(i).getId());

                if(!(tempDis.compareTo(dis) == 1)){
                    index = i;
                    dis = tempDis;
                }
            }

            /**
             *  遍历所有离当前点最近的点
             */
            for(int i=0;i<unhandled.size();i++){
                BigDecimal currentDis = this.pointsRep.getDis(header.getLocation().getId(),unhandled.get(i).getId());
                if(dis.compareTo(currentDis) == 0){
                    LocationShortRoute locationShortRoute = new LocationShortRoute();
                    //设置经纬度信息
                    locationShortRoute.setLocation(unhandled.get(i));
                    //设置上一经纬度ID
                    locationShortRoute.setPreviousId(header.getLocation().getId());
                    //设置到上一经纬度的距离
                    locationShortRoute.setPreviousDis(currentDis);

                    snakeHandle(getLocationList(unhandled,i),getShortRouteList(shortRoutes,locationShortRoute));

                    break;
                }
            }
        }else{
            if(unhandled!=null && unhandled.size()==1){
                BigDecimal dis = this.pointsRep.getDis(header.getLocation().getId(),unhandled.get(0).getId());

                LocationShortRoute locationShortRoute = new LocationShortRoute();
                //设置经纬度信息
                locationShortRoute.setLocation(unhandled.get(0));
                //设置上一经纬度ID
                locationShortRoute.setPreviousId(header.getLocation().getId());
                //设置到上一经纬度的距离
                locationShortRoute.setPreviousDis(dis);

                List<LocationShortRoute> shortRoutesList = getShortRouteList(shortRoutes,locationShortRoute);

                /**
                 * 设置头到尾的距离信息
                 */
                shortRoutes.get(0).setPreviousId(shortRoutes.get(shortRoutes.size()-1).getLocation().getId());
                shortRoutes.get(0).setPreviousDis(this.pointsRep.getDis(shortRoutes.get(0).getLocation().getId(),shortRoutes.get(shortRoutes.size()-1).getLocation().getId()));

                /**
                 * 根据最短路径列表生成经纬度列表信息
                 */
                globalList.add(shortRoutesList);
            }
        }
    }

    /**
     * 返回不包含某个下标信息的list
     *
     * @param unhandled
     * @return
     */
    private List<Location> getLocationList(List<Location> unhandled,int index){
        List<Location> list = new ArrayList<>();
        for(int i=0;i<unhandled.size();i++){
            //移除下标为index的数据
            if(i != index){
                list.add(unhandled.get(i));
            }
        }

        return list;
    }

    /**
     * 返回追加新信息后的list
     * @return
     */
    private List<LocationShortRoute> getShortRouteList(List<LocationShortRoute> shortRoutes , LocationShortRoute locationShortRoute){
        List<LocationShortRoute> list = new ArrayList<>();
        for(int i=0;i<shortRoutes.size();i++){
            list.add(shortRoutes.get(i));
        }

        //将最新数据追加到list
        list.add(locationShortRoute);

        return list;
    }

    /**
     * 根据一条最优路径进行截取，获取分段路径
     * @return
     */
    private Location[][] getBestRoute(){
        /**
         * 根据需要分的组 和 经纬度数量，确定每组有多少元素
         *
         * todo 这一块可以进行单独优化，现有处理方案是强制将多余的从头分配给各块，每一块分一个
         */
        int group = this.pointsRep.getGroup();
        int pointCount = globalList.get(0).size();
        //每组需要分的数量
        int[] groupCount = new int[group];

        int origin = pointCount/group;
        int more = pointCount%group;

        for(int i=0;i<group;i++){
            groupCount[i] = origin;
        }

        for(int i=0;i<more;i++){
            groupCount[i] = groupCount[i] + 1;
        }

        /**
         * 根据每组需要分得的数量对每条线路进行分组，获取最优路径
         */

        //最短路径下标
        int bestIndex = -1;
        //最短路径总长度
        BigDecimal sumRoute = null;
        //最短路径列表
        List<LocationShortRoute> bestShortRoute = null;
        for(int i=0;i<globalList.size();i++){
            BestRoute currBestRoute = getCurrBestRoute(groupCount,globalList.get(i));

            /**
             * 如果最短路径为null,就将当前路径作为最短路径进行赋值
             * 如果最短路径大于当前路径的值，将当前路径作为最短路径进行赋值
             */
            if(sumRoute == null){
                sumRoute = currBestRoute.getSumRoute();
                bestIndex = i;
                bestShortRoute = currBestRoute.getList();
            }else if(sumRoute.compareTo(currBestRoute.getSumRoute()) == 1){
                sumRoute = currBestRoute.getSumRoute();
                bestIndex = i;
                bestShortRoute = currBestRoute.getList();
            }
        }

        return getBestRoute(groupCount,bestShortRoute);
    }

    /**
     * 根据分组数和当前路径获取最优分组路径
     *
     * 最优路径形成一个环，选择每一个点作为起点，重新生成列表，用于后续分组。并且计算分组后的路径长度，选择路径加和最小的作为最优路径
     *
     * @param groupCount
     * @param shortRoutes
     * @return
     */
    private BestRoute getCurrBestRoute(int[] groupCount, List<LocationShortRoute> shortRoutes){
        int index = 0;
        BigDecimal sumRouteLen = null;
        List<LocationShortRoute> bestRoute = null;

        /**
         *  循环让所有点作为起点
         */
        for(int i=0;i<shortRoutes.size();i++){
            /**
             * 根据起点生成新的列表
             */
            List<LocationShortRoute> currShortRoute = new ArrayList<>();
            for(int j=0;j<shortRoutes.size();j++){
                //偏移下标
                int offset = j + i;
                if(offset < shortRoutes.size()){
                    currShortRoute.add(shortRoutes.get(offset));
                }else{
                    //偏移下标大于列表下标，则减去列表长度，从头添加
                    int offsetIndex = offset - shortRoutes.size();
                    currShortRoute.add(shortRoutes.get(offsetIndex));
                }
            }

            /**
             * 根据分组数和列表计算分组后路径总长度
             */
            BigDecimal routeLength = getRouteLength(groupCount,shortRoutes);

            if(sumRouteLen == null){
                sumRouteLen = routeLength;
                index = i;
                bestRoute = currShortRoute;
            }else if(sumRouteLen.compareTo(routeLength) == 1){
                sumRouteLen = routeLength;
                index = i;
                bestRoute = currShortRoute;
            }

        }

        /**
         * 封装返回对象信息
         */
        BestRoute bestRouteInfo = new BestRoute();
        //路径长度
        bestRouteInfo.setSumRoute(sumRouteLen);
        //路径列表
        bestRouteInfo.setList(bestRoute);

        return bestRouteInfo;
    }

    /**
     * 根据分组数和经纬度列表获取路径长度
     * @return
     */
    private BigDecimal getRouteLength(int[] groupCount,List<LocationShortRoute> shortRoutes){
        int groupCountIndex = 0;
        int sumGroupCount = 0;
        BigDecimal sumRoute = null;
        for(int i = 0;i<shortRoutes.size();i++){
            /**
             *  判断是起点还是和分组数加和相等
             *  不相等时进行路径加和计算，相等或为起点时切换到下一分组进行计算
             *  等于分组加和时，说明计算完成，终止循环
             */
            if(i == 0){
                //判断是否是起点
                groupCountIndex = 0;
                sumGroupCount = groupCount[0];

            }else if(i == sumGroupCount){
                //判断是否和分组数加和相等
                groupCountIndex += 1;
                if(groupCountIndex < groupCount.length){
                    sumGroupCount += groupCount[groupCountIndex];
                }else{
                    break;
                }

            }else{
                //进行路径加和计算
                if(sumRoute == null){
                    sumRoute = this.pointsRep.getDis(shortRoutes.get(i).getLocation().getId(),shortRoutes.get(i-1).getLocation().getId());
                }else{
                    BigDecimal currentLen = this.pointsRep.getDis(shortRoutes.get(i).getLocation().getId(),shortRoutes.get(i-1).getLocation().getId());
                    sumRoute = sumRoute.add(currentLen);
                }
            }
        }

        return sumRoute;
    }

    /**
     * 根据分组数和列表获取路径分组
     * @param groupCount
     * @param shortestRoute
     * @return
     */
    private Location[][] getBestRoute(int[] groupCount,List<LocationShortRoute> shortestRoute){
        Location[][] locations = new Location[groupCount.length][shortestRoute.size()];
        int groupCountSum = 0;
        int currentIndex = 0;

        for(int i=0;i<groupCount.length;i++){
            groupCountSum += groupCount[i];

            for(int j = 0;j<groupCount[i];j++){
                locations[i][j] = shortestRoute.get(currentIndex).getLocation();

                currentIndex++;
            }
        }

        return locations;
    }

    /**
     * 获取所有可能分组
     * @return
     */
    private List<int[]> getAllGroup(){
        /**
         * 均分所有点，多余的点，进行全排
         */
        int group = this.pointsRep.getGroup();
        int pointCount = globalList.get(0).size();
        //每组需要分的数量
        int[] groupCount = new int[group];

        int origin = pointCount/group;
        int more = pointCount%group;

        for(int i=0;i<group;i++){
            groupCount[i] = origin;
        }

        /**
         * 将所有多余的数分别放在所有平均的数上,获取所有可能分组
         */
        return null;
    }
}
